In classical reinforcement learning agents accept arbitrary short term loss for long term gain when exploring their environment. This is infeasible for safety critical applications such as robotics, where even a single unsafe action may cause system failure or harm the environment. In this paper, we address the problem of safely exploring finite Markov decision processes (MDP). We define safety in terms of an a priori unknown safety constraint that depends on states and actions and satisfies certain regularity conditions expressed via a Gaussian process prior. We develop a novel algorithm, SAFEMDP, for this task and prove that it completely explores the safely reachable part of the MDP without violating the safety constraint. To achieve this, it cautiously explores safe states and actions in order to gain statistical confidence about the safety of unvisited state-action pairs from noisy observations collected while navigating the environment. Moreover, the algorithm explicitly considers reachability when exploring the MDP, ensuring that it does not get stuck in any state with no safe way out. We demonstrate our method on digital terrain models for the task of exploring an unknown map with a rover.

The paper is well-written and clear. The proposed idea is interesting. I have the following comments/questions: 1) Does the Liptschiz assumption hold here with a probability or is it assumed to always hold? 2) Figure 1: should it be \bar{s}_2 instead of s_2 in the caption? The use of bar for non-sets is confusing. I do not see the need for the last intersection in Equation 4. 4) When you repeatedly apply Equation 4, the number of states that satisfy the safety constraint shrinks because you use Liptschiz in the worst scenario sense.